package leetcode;

import java.util.*;

public class LC_stack {
    public static void main(String[] args) {
        LC_stack lc = new LC_stack();
        System.out.println(lc.largestRectangleArea(new int[]{0,9}));
        System.out.println(lc.largestRectangleArea(new int[]{2,1,5,6,2,3}));
        System.out.println(lc.largestRectangleArea(new int[]{73,74,75,71,69,72,76,73}));
        System.out.println(Arrays.toString(lc.dailyTemperatures(new int[]{73,74,75,71,69,72,76,73})));
        System.out.println(lc.decodeString("3[a2[c]]"));
        System.out.println(lc.decodeString("abc3[cd]xyz"));
        System.out.println(lc.isValid("([])"));
        System.out.println(lc.isValid("()"));
        System.out.println(lc.isValid("()[]{}"));
    }
    /*
        LeetCode  20题
     */
    public boolean isValid(String s) {
        Map<Character,Character> map = new HashMap<>();
        map.put(')','(');
        map.put('}','{');
        map.put(']','[');
        Stack<Character> queue = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)){
                if (queue.empty()) return false;
                Character poll = queue.pop();
                if (!Objects.equals(map.get(c),poll)) return false;
            }else {
                queue.add(c);
            }
        }
        return queue.empty();
    }
    /*
        LeetCode 155题
     */
    class MinStack {

        Stack<Integer> stack = new Stack<>();
        int min = 0;
        public MinStack() {

        }

        public void push(int val) {
            if (stack.isEmpty()){
                stack.push(0);
                min = val;
            }else {
                stack.push(val - min);
                if (val < min) min = val;
            }
        }

        public void pop() {
            if (!stack.empty()){
                Integer pop = stack.pop();
                if (pop < 0){
                    min = min - pop;
                }
            }
        }

        public int top() {
            if (!stack.isEmpty()){
                Integer peek = stack.peek();
                return peek < 0 ? min : min + peek;
            }
            return -1;
        }

        public int getMin() {
            if (!stack.isEmpty()){
                return min;
            }
            return -1;
        }
    }
    /*
        LeetCode 394题
     */
    public String decodeString(String s) {
        Stack<Object> stack = new Stack<>();
        char[] chars = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (char aChar : chars) {
            if (aChar >= '0' && aChar <= '9') {
                sb.append(aChar);
                continue;
            }
            if (!sb.isEmpty()) {
                stack.push(sb.toString());
                sb.setLength(0);
            }
            if (aChar == ']'){
                Object pop = stack.pop();
                while(!Objects.equals(pop,'[')){
                    sb.insert(0,pop);
                    pop = stack.pop();
                }
                pop = stack.pop();
                String ss = sb.toString();
                sb.append(ss.repeat(Math.max(0, Integer.parseInt(pop.toString()) - 1)));
                stack.push(sb.toString());
                sb.setLength(0);
            }else
                stack.push(aChar);
        }
        for (Object o : stack) {
            sb.append(o);
        }
        return sb.toString();
    }
    /*
        LeetCode 739题
     */
    public int[] dailyTemperatures(int[] temperatures) {
        if (temperatures.length < 1) return new int[0];
        int[] ans = new int[temperatures.length];
        Stack<Integer> nums = new Stack<>();
        nums.push(0);
        for (int i = 1; i < temperatures.length; i++) {
            while(!nums.isEmpty() && temperatures[i] > temperatures[nums.peek()]){
                ans[nums.peek()] = i - nums.pop();
            }
            nums.push(i);
        }
        return ans;
    }
    /*
        LeetCode 84题
        矩形面积为宽*高，高为当前值，宽为当前坐标右边比自己小的坐标减左边比自己小的坐标的值
     */
    public int largestRectangleArea(int[] heights) {
        int[] left = new int[heights.length];
        int[] right = new int[heights.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < heights.length; i++) {
            while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
                stack.pop();
            }
            if (stack.isEmpty()) left[i] = 0;
            else left[i] = stack.peek();
            stack.push(i);
        }
        stack.clear();
        for (int i = heights.length - 1; i >= 0; i--) {
            while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
                stack.pop();
            }
            if (stack.isEmpty()) right[i] = heights.length;
            else right[i] = stack.peek();
            stack.push(i);
        }
        System.out.println(Arrays.toString(left));
        System.out.println(Arrays.toString(right));
        int max = 0;
        for (int i = 0; i < heights.length; i++) {
            max = Math.max(max, (right[i] - left[i] - 1) * heights[i]);
        }
        return max;
    }
}